// https://leetcode.cn/problems/increasing-order-search-tree/
// Created by ade on 2022/8/19.
//
#include <iostream>
#include <vector>


using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode *head = nullptr;
    TreeNode *index = nullptr;

    TreeNode *increasingBST(TreeNode *root) {
        dfs(root);
        return head;
    }

    void dfs(TreeNode *node) {
        if (!node) return;
        dfs(node->left);
        TreeNode *tmp = new TreeNode(node->val);
        if (!head) {
            head = tmp;
        } else {
            index->right = tmp;
        }
        index = tmp;
        dfs(node->right);
    }
};